index.md (676B)
1 +++ 2 title = "Prim's algorithm" 3 +++ 4 # Prim's algorithm 5 ## What is it? 6 7 Finds *minimum spanning tree* for a connected weighted undirected graph. Faster in dense graphs with more edges than vertices. 8 9 Spanning tree: connected acyclic subgraph that contains all vertices of the graph 10 11 weight of tree: sum of weights on all the tree’s edges 12 minimum spanning tree: spanning tree of smallest weight 13 14 **Steps:** 15 1. Select any vertex to be first of T 16 17 2. Consider which edge connects vertices in T to vertices outside T. Pick any one with min weight. Add edge and vertex to T. 18 19 3. Repeat step 2 until T has every vertex of graph. 20 21 